package com.leetcode.根据数据结构分类.栈;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/12/20
 * @description: 155. 最小栈
 * https://leetcode-cn.com/problems/min-stack/
 */
public class A_155_最小栈 {

	public static void main(String[] args) {
		MinStack minStack = new MinStack();
		minStack.push(-2);
		minStack.push(0);
		minStack.push(-3);
		//返回 -3.
		int min = minStack.getMin();
		System.out.println("min = " + min);
		minStack.pop();
		//返回 0
		int top = minStack.top();
		System.out.println("top = " + top);
		//返回 -2
		min = minStack.getMin();
		System.out.println("min = " + min);
	}

	/**
	 * 这是个 数据结构设计题
	 * 我的设计：
	 * 1.栈通过动态数组进行实现；
	 * 2.通过 另一个动态数组 设计上一个数组的大小；
	 * --
	 * 反思：
	 * 我的设计太复杂了，没有必要存储大小顺序的索引！
	 * 就像 TopK 与 二叉搜索树，找出规律找出最省事的步骤。
	 * 看了官方题解的思路，于是有了 MinStack2
	 */
	static class MinStack {

		/**
		 * 数据层
		 * eg.3,2,6
		 */
		private List<Integer> data = new ArrayList<>();

		/**
		 * 索引层(记录 data 数组中第几小的元素)
		 * eg.1,0,2
		 * 说明：最小的元素在 data[1] ,最大的索引在 data[2]
		 */
		private List<Integer> indexArray = new ArrayList<>();

		/**
		 * initialize your data structure here.
		 */
		public MinStack() {

		}

		public void push(int x) {
			data.add(x);
			int indexEnd = data.size() - 1;

			if (indexEnd == 0) {
				indexArray.add(0);
				return;
			}
			int tempIndex = indexEnd;

			//indexArray.add(indexEnd);
			for (int i = indexEnd - 1; i >= 0; i--) {
				if (data.get(indexArray.get(i)) > x) {
					//将 i 和 tempIndex 进行交换
					//不进行交换，太麻烦了！
//					int temp = indexArray.get(i);
//					indexArray.set(i, tempIndex);
//					indexArray.set(tempIndex, temp);
					//tempIndex = i;
					tempIndex = i;
				} else {
					//indexArray.add(i + 1, indexEnd);

					break;
				}
			}
			indexArray.add(tempIndex, indexEnd);

		}

		/**
		 * 删除栈顶元素
		 * 分析：
		 */
		public void pop() {
			int index = data.size() - 1;
			data.remove(index);
			for (int i = 0; i < indexArray.size(); i++) {
				if (indexArray.get(i) == index) {
					indexArray.remove(i);
					break;
				}
			}
		}

		/**
		 * @return
		 */
		public int top() {
			return data.get(data.size() - 1);
		}

		public int getMin() {
			return data.get(indexArray.get(0));
		}

	}

	/**
	 * 分析：
	 * 只要记录 出栈/入栈 时刻的最小值即可
	 */
	static class MinStack2 {

		/**
		 * 数据栈
		 */
		private Stack<Integer> dataStack = new Stack<>();

		/**
		 * 辅助栈
		 * 记录 入栈/出栈 时（每一次）的最小值
		 */
		private Stack<Integer> minStack = new Stack<>();


		/**
		 * initialize your data structure here.
		 */
		public MinStack2() {

		}

		public void push(int x) {
			dataStack.push(x);
			if (!minStack.isEmpty()) {
				Integer value = minStack.peek();
				if (x < value) {
					minStack.push(x);
				}else {
					minStack.push(value);
				}
			}else {
				minStack.push(x);
			}
		}

		/**
		 * 删除栈顶元素
		 */
		public void pop() {
			dataStack.pop();
			minStack.pop();
		}

		/**
		 * @return
		 */
		public int top() {
			return dataStack.peek();
		}

		public int getMin() {
			return minStack.peek();
		}
	}
}
